home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 6985 < prev    next >
Encoding:
Text File  |  1996-08-05  |  4.9 KB  |  137 lines
  1. Path: news.microsoft.com!news
  2. From: a-cnadc@microsoft.com (Dann Corbit)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Tough FACTORIAL math problem...
  5. Date: 16 Feb 1996 23:17:18 GMT
  6. Organization: Microsoft Corporation
  7. Message-ID: <4g339u$dkk@news.microsoft.com>
  8. References: <4fr8be$ass@news.iconn.net> <31224679.6193@born.com> <4fv16m$cuj@winx03.informatik.uni-wuerzburg.de>
  9. NNTP-Posting-Host: 157.57.171.202
  10. Mime-Version: 1.0
  11. X-Newsreader: WinVN 0.93.14
  12.  
  13. In article <4fv16m$cuj@winx03.informatik.uni-wuerzburg.de>, schoof@informatik.uni-wuerzburg.de says...
  14. { Snip }
  15. >int factorial_lsd(int n)
  16. >{
  17. >  int result=1, i;
  18. >
  19. >  if(n>1) 
  20. >    for(i=1;i<=n;i++)
  21. >    {
  22. >      result*=i;
  23. >      while(result%10==0) result/=10;
  24. >      result%=100;
  25. >    }
  26. >  return temp%10;
  27. >}
  28. >
  29.  
  30.  <Dik.Winter@cwi.nl> has shown me the error of my
  31. ways, and I repent in dust and ashes ;>)
  32.  
  33. Jochen's program is almost there, but it will fail 
  34. when the factor produces two zeros.  Here is one 
  35. that will do the job.  The number "100000L" has to
  36. be chosen carefully, so that it will not overflow
  37. when multiplied by the next factor, and so that it
  38. will not truncated needed digits of precision.  It 
  39. must be larger than n and smaller than MAX_LONG/n:
  40.  
  41. long factorial_lsd( long n )
  42. {
  43.    long result=1, i, count;
  44.  
  45.    if ( n > 1 )
  46.       for ( i=1; i<=n; i++ )
  47.       {
  48.          result *= i;
  49.          count = 0;
  50.          while( result%10 == 0 )
  51.          {
  52.             result /= 10;
  53.             count++;
  54.          }
  55.          result %= 100000L;
  56.       }
  57.    return result%10;
  58. }
  59. #define TEST
  60. #ifdef TEST
  61.  
  62. #include <stdio.h>
  63. #include <stdlib.h>
  64. /****************************************************************
  65. 100!
  66.       933 26215 44394 41526 81699 23885 62667 00490 71596 82643
  67.     81621 46859 29638 95217 59999 32299 15608 94146 39761 56518
  68.     28625 36979 20827 22375 82511 85210 91686 40000 00000 00000
  69.     00000 00000
  70.  
  71. 200!
  72.     78865 78673 64790 50355 23632 13932 18506 22951 35977 68717
  73.     32632 94742 53324 43594 49963 40334 29203 04284 01198 46239
  74.     04177 21213 89196 38830 25764 27902 42637 10506 19266 24952
  75.     82993 11134 62857 27076 33172 37396 98894 39224 45621 45166
  76.     42402 54033 29186 41312 27428 29485 32775 24242 40757 39032
  77.     40321 25740 55795 68660 22603 19041 70324 06235 17008 58796
  78.     17892 22227 89623 70389 73747 20000 00000 00000 00000 00000
  79.     00000 00000 00000 00000 00000
  80.  
  81. 300!
  82.     30605 75122 16440 63603 53704 61297 26862 93885 88804 17357
  83.     69994 16776 74125 94765 33176 71686 74655 15291 42247 75733
  84.     49939 14788 87017 26368 86426 39077 59003 15422 68429 27906
  85.     97455 98412 25476 93027 19546 04008 01221 57762 52176 85425
  86.     59653 56903 50678 87252 64321 89626 42993 65204 57644 88303
  87.     88909 75394 34896 25436 05322 59807 76521 27082 24376 39449
  88.     12012 86786 75368 30571 22936 81943 64995 64604 98166 45022
  89.     77165 00185 17654 64693 40112 22603 47297 24066 33325 85835
  90.     06870 15016 97941 68850 35375 21375 54910 28912 64071 57154
  91.     83028 22849 37952 63658 01452 35233 15693 64822 33436 79925
  92.     45940 95276 82060 80622 32812 38738 38808 17049 60000 00000
  93.     00000 00000 00000 00000 00000 00000 00000 00000 00000 00000
  94.     00000 00000 00000
  95.  
  96. 400!
  97.      6403 45228 46623 89526 23479 70319 50300 58507 02583 02600
  98.     29594 58684 44594 28023 97169 18683 14362 78478 64746 32646
  99.     76294 35057 50358 56810 84829 81628 83517 43522 89619 88646
  100.     80299 79373 41654 15083 81624 26461 94235 23070 46244 32501
  101.     51144 48670 89066 27739 14918 11733 19559 96440 70954 96713
  102.     45290 47702 03224 34911 21079 75932 80795 10154 53726 67251
  103.     62787 78900 09349 76376 57103 26350 33153 39653 49868 38683
  104.     13393 52024 37378 81577 86791 50631 18587 02618 27016 98197
  105.     40062 98302 53085 91298 34616 22723 04558 33952 07596 11505
  106.     30223 60868 10433 29725 51948 52674 43223 24386 69948 42240
  107.     42325 99805 55161 06359 42376 96139 92319 17134 06385 89965
  108.     37970 14782 72066 06320 21737 94720 10321 35662 46138 09077
  109.     94230 45973 60699 56759 58360 96158 71512 99138 22286 57857
  110.     95493 61617 65448 04532 22007 82581 84008 48436 41559 12294
  111.     54275 38480 35583 74518 02267 59000 61399 56014 55952 06127
  112.     21119 29181 05032 49100 80000 00000 00000 00000 00000 00000
  113.     00000 00000 00000 00000 00000 00000 00000 00000 00000 00000
  114.     00000 00000 00000 00000
  115. ***************************************************************/
  116.  
  117. int main()
  118. {
  119.    printf("last digit of 100! = %ld.  Should be '4'\n", factorial_lsd( 100 ));
  120.    printf("last digit of 200! = %ld.  Should be '2'\n", factorial_lsd( 200 ));
  121.    printf("last digit of 300! = %ld.  Should be '6'\n", factorial_lsd( 300 ));
  122.    printf("last digit of 400! = %ld.  Should be '8'\n", factorial_lsd( 400 ));
  123.    return 0;
  124. }
  125. #endif
  126. /* On my machine, I get:
  127. last digit of 100! = 4.  Should be '4'
  128. last digit of 200! = 2.  Should be '2'
  129. last digit of 300! = 6.  Should be '6'
  130. last digit of 400! = 8.  Should be '8'
  131. **************************************/
  132.  
  133. -- 
  134. The opinions expressed in this message are my own personal views 
  135. and do not reflect the official views of Microsoft Corporation.
  136.  
  137.